In social networks, certain nodes (e.g., users, entities, etc.) influence other nodes for various reasons and by various degrees. For example, a prominent food critic on a micro-blogging service may profoundly influence the interests of his or her followers based on a posting that is critical of a particular restaurant. Such influence impacts not only nodes in the immediate proximity to the influencing node, but the influence can also propagate throughout the social network, with varying degrees of effectiveness.
Diffusion is a graph process that models such phenomena as the spread of information by word-of-mouth throughout a population. Diffusion can also be applied to understanding other phenomena, such as the spread of epidemic disease throughout a population. Generally, diffusion models the influence a particular node (e.g., a person) exerts on another node in a network and how that influence propagates to other nodes in the network.
Modern social networks define populations in which influence can be characterized using diffusion modeling. Understanding the ways in which influence can spread through such networks can be beneficial, for example, in advertising activities. A prominent application of diffusion modeling in a social network is a viral marketing campaign that aims to use a small number of targeted messages to initiate cascades of influence to create global increases in product adoption. To this end, it is helpful to identify those individuals who can exert the most influence within the social network and thereby maximize the proliferation of the messaging and the adoption of the product. However, the influence-maximization problem presents a significant computational challenge for predicting which individuals should be targeted with the messaging in order to maximize the magnitude of the resulting cascade, particularly in the context of constrained computational budgets and increasingly complex and continually growing networks.